package tree;

/**
 * @author : Rookie
 * @description : 有序数组转化为二叉平衡搜索树
 * @date : 2023/11/4
 */
public class SortedArrToBinaryBalanceSearchTree {

    public static void main(String[] args) {
        int[] arr = new int[] {-10,-3,0,5,9};
        TreeNode root = buildBinaryBalanceSearchTree(arr,0,arr.length-1);
        BinaryTreeUtil.Traversal.sequenceTraversal(root);
    }

    private static TreeNode buildBinaryBalanceSearchTree(int[] arr,int left,int right) {
        if (left > right) {
            return null;
        }
        // 这么写是为了当left right为int的最大值时，相加越界
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(arr[mid]);
        // 此处范围是[left,mid-1]
        root.left = buildBinaryBalanceSearchTree(arr,left,mid-1);
        // 此处范围是[mid+1,right]
        root.right = buildBinaryBalanceSearchTree(arr,mid+1,right);
        return root;
    }
}
